# https://leetcode.cn/problems/snakes-and-ladders/description/
from queue import Queue


class Solution:
    def snakesAndLadders(self, board: list[list[int]]) -> int:
        def exchange(n: int, number: int) -> (int, int):
            if n & 1:
                x = n - 1 - (number - 1) // n
                if x & 1:
                    return x, n - 1 - (number - 1) % n
                else:
                    return x, (number - 1) % n
            else:
                x = n - 1 - (number - 1) // n
                if x & 1:
                    return x, (number - 1) % n
                else:
                    return x, n - 1 - (number - 1) % n

        boardSize = len(board)
        visited = [False for _ in range(boardSize * boardSize + 1)]
        pt = Queue()
        ptSet = set()
        pt.put(1)
        ptSet.add(1)
        step = 0

        while pt.qsize():
            step += 1
            qSize = pt.qsize()
            for _ in range(qSize):
                node = pt.get()
                visited[node] = True
                for i in range(node + 1, min(node + 6, boardSize * boardSize) + 1):
                    if i == boardSize * boardSize:
                        return step
                    nextNode = exchange(boardSize, i)
                    if board[nextNode[0]][nextNode[1]] != -1:
                        if board[nextNode[0]][nextNode[1]] == boardSize * boardSize:
                            return step
                        if not visited[board[nextNode[0]][nextNode[1]]]:
                            pt.put(board[nextNode[0]][nextNode[1]])
                    else:
                        if not visited[i] and i not in ptSet:
                            pt.put(i)
                            visited[i] = True
                            ptSet.add(i)
        return -1
